/* 
给定一个二叉树，返回它的中序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3
输出: [1,3,2]
来源: LeetCode第94题 
*/

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
// 递归方式:
var inorderTraversal = function (root) {
    const arr = [];
    const traverse = (root) => {
        if (root === null) return;
        traverse(root.left);
        arr.push(root.val);
        traverse(root.right);
    }
    traverse(root);
    return arr;
};

// 非递归方式
var inorderTraversal = function (root) {
    if (root === null) return [];
    const stack = [],
        res = [];
    let p = root;
    while (stack.length || p) {
        while (p) {
            stack.push(p);
            p = p.left;
        }
        const node = stack.pop();
        res.push(node.val);
        // 右节点并没有入栈，所以第一个while的判断条件要加一个 p
        // 若这里把右节点入栈，若这个右节点为null，会导致下一轮循环出现 "Cannot read property 'val' of null"错误
        p = node.right;
    }
    return res;
};